堆排序(Heap Sort)
概述
堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。
什么是堆
堆的实现通过构造二叉堆,实为二叉树的一种分支。这种数据结构具有以下性质:
- 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
- 堆总是一个完全二叉树,即除了最底层外,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
将根节点最大的堆叫做最大堆,而将根节点最小的堆叫做最小堆。
堆排序中如何表示堆
由于堆总是一个完全二叉树这一特性,这使得堆可以利用数组来表示,如下图所示。
对于给定的某个节点的下标i,可以很容易的计算出这个节点的父节点、左右孩子节点的下标:
- Parent(i) = floor((i - 1) / 2),i节点的父节点下标
- Left(i) = 2i * 1,i节点的左子节点下标
- Right(i) = 2 * (i - 1),i节点的右子节点下标
堆排序原理(以最大堆为例)
堆排序就是把最大堆的堆顶取出,将剩余的堆继续调整为最大堆,再将堆顶的数值取出,不断重复这一过程,直至堆中只剩下一个节点为止。堆中定义以下几种操作:
- 最大堆调整(MaxHeapify):将堆的末端子节点作调整,使得子节点永远小于父节点
- 创建最大堆(BuildMaxHeap):将堆所有数据重新排序
- 推排序(HeapSort):移除在第一个数据的根节点,bin并做最大堆调整的递归运算
最大堆调整(MaxHeapify)
最大堆调整的作用是保持最大堆的性质,是整个算法的核心部分。它内部的算法其实决定了堆到底是最大堆还是最小堆。
代码部分如下所示:
1 | // array代表需要排序的数组部分 |
非递归实现版本
1 | public void maxHeapAdjustWhile(int index, int heapSize) { |
创建最大堆(BuildMaxHeap)
创建最大堆的作用是将一个数组转换为一个最大堆。倘若堆中有n个元素,那么BuildMaxHeap就从Parent(n)开始(因为Parent(n)的节点刚刚好指向最后一个元素的父节点),从下往上地调用MaxHeapify。
代码结构如下所示:
1 | public void buildMaxHeap(int heapSize) { |
推排序(HeapSort)
堆排序是堆排序算法的接口算法部分,HeapSort先调用BuildMaxHeap将传递来的数组转换为最大堆,然后将最大堆堆顶元素与堆底最后一个元素对换,然后再重新调用MaxHeapify来保证最大堆的性质。
代码结构如下所示:
1 | public int[] maxHeapSort() { |
时间与空间复杂度
最优时间复杂度为O(nlogn),最坏时间复杂度O(nlogn)。
总空间复杂度为O(n),辅助空间复杂度O(1)。
参考资料